package week_03;

/**
 * 329. 矩阵中的最长递增路径
 * 给定一个m x n 整数矩阵matrix ，找出其中 最长递增路径 的长度。
 * <p>
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
 * 输出：4
 * 解释：最长递增路径为[1, 2, 6, 9]。
 * 示例 2：
 * <p>
 * <p>
 * 输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
 * 输出：4
 * 解释：最长递增路径是[3, 4, 5, 6]。注意不允许在对角线方向上移动。
 * 示例 3：
 * <p>
 * 输入：matrix = [[1]]
 * 输出：1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LongestIncreasingPath_DFS_329 {
    int m;
    int n;
    int[][] answer;
    int ans;
    //                U,L,R,D
    int[] dx = new int[]{-1, 0, 0, 1};
    int[] dy = new int[]{0, -1, 1, 0};

    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        answer = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                answer[i][j] = -1;
            }
        }
        ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, howFar(matrix, i, j));
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println(answer[i][j]);
            }
        }
        return ans;
    }

    private int howFar(int[][] matrix, int x, int y) {
        // 曾经搜索过的点记忆化存储结果 直接返回
        if (answer[x][y] != -1) return answer[x][y];
        answer[x][y] = 1;
        // 四个方向展开搜索方向
        // 一定会更新到正确的答案
        for (int i = 0; i < 4; i++){
            int nx= x+dx[i];
            int ny =y+dy[i];
            // 判断边界 是否越界
            if(nx<0||ny<0||nx>=m||ny>=n) continue;
            //是否符合向下搜的条件
            if(matrix[nx][ny]>matrix[x][y]){
                // 对衍生出去的出边返回结果依次做一个比对更新
                answer[x][y]=Math.max(answer[x][y],howFar(matrix,nx,ny)+1);
            }
        }
        return answer[x][y];
    }
}
